package com.mlh.matrix;

/**
 * @author 缪林辉
 * @date 2024/8/19 22:02
 * @DESCRIPTION
 */
//编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
// 每行的元素从左到右升序排列。
// 每列的元素从上到下升序排列。
public class 搜索二维矩阵2 {
    //方法1：全体遍历
    //方法2：每行二分查找
    //方法3：本方法 Z字形查找（杨氏矩阵查找算法）
    public boolean method1(int[][] matrix, int target) {
        int rowLen=matrix.length,colLen=matrix[0].length;
        int row=0,col=colLen-1;
        while(row<rowLen&&col>=0){
            if(matrix[row][col]>target){
                col--;
            }else if(matrix[row][col]<target){
                row++;
            }else{
               return true;
            }
        }
        return false;
    }
    // 开题解  可以用平衡二叉树来理解
    public boolean practice(int[][] matrix, int target) {
        int row=matrix.length,col=matrix[0].length;
        int rowStart=0,colStart=col-1;
        while(rowStart<row&&colStart>=0){
            if(matrix[rowStart][colStart]>target){
                colStart--;
            } else if (matrix[rowStart][colStart]<target) {
                rowStart++;
            }else {
                return true;
            }
        }
        return false;
    }

}
